Paper 2021/500

Order-C Secure Multiparty Computation for Highly Repetitive Circuits

Gabrielle Beck, Aarushi Goel, Abhishek Jain, and Gabriel Kaptchuk

Abstract

Running secure multiparty computation (MPC) protocols with hundreds or thousands of players would allow leveraging large volunteer networks (such as blockchains and Tor) and help justify honest majority assumptions. However, most existing protocols have at least a linear (multiplicative)dependence on the number of players, making scaling difficult. Known protocols with asymptotic efficiency independent of the number of parties (excluding additive factors) require expensive circuit transformations that induce large overheads. We observe that the circuits used in many important applications of MPC such as training algorithms used to create machine learning models have a highly repetitive structure. We formalize this class of circuits and propose an MPC protocol that achieves O(|C|) total complexity for this class. We implement our protocol and show that it is practical and outperforms O(n|C|) protocols for modest numbers of players.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
Secure multiparty computation
Contact author(s)
gbeck @ cs jhu edu
aarushig @ cs jhu edu
abhishek @ cs jhu edu
kaptchuk @ bu edu
History
2021-11-03: revised
2021-04-19: received
See all versions
Short URL
https://ia.cr/2021/500
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/500,
      author = {Gabrielle Beck and Aarushi Goel and Abhishek Jain and Gabriel Kaptchuk},
      title = {Order-C Secure Multiparty Computation for Highly Repetitive Circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/500},
      year = {2021},
      url = {https://eprint.iacr.org/2021/500}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.